package com.cqs.leetcode.tree.Trie;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * lixw
 * 2021/11/14
 **/
public class MapSumPairs677 {

    private TreeNode root;

    private class TreeNode {
        //权重
        TreeNode[] children = new TreeNode[26];
        boolean isLeaf = false;
        int weight;
    }

    public MapSumPairs677() {
        root = new TreeNode();
    }

    public void insert(String key, int val) {
        TreeNode rt = this.root;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            TreeNode node = rt.children[c - 'a'];
            if (node == null) {
                node = new TreeNode();
                rt.children[c - 'a'] = node;
            }
            if (i == key.length() - 1) {
                node.weight = val;
                node.isLeaf = true;
            }
            rt = node;
        }
    }


    //字典树+BFS
    public int sum(String prefix) {
        int sum = 0;
        Queue<TreeNode> q = new ArrayDeque<>();
        TreeNode rt = root;
        for (int i = 0; i < prefix.length(); i++) {
            rt = rt.children[prefix.charAt(i) - 'a'];
            if (rt == null) {
                break;
            }
        }
        if (rt == null) return sum;
        q.add(rt);
        while (q.size() > 0) {
            int num = q.size();
            while (-- num >= 0) {
                TreeNode node = q.remove();
                if (node.isLeaf) {
                    sum += node.weight;
                }else {
                    for (int i = 0; i < 26; i++) {
                        if (node.children[i] != null) {
                            q.add(node.children[i]);
                        }
                    }
                }

            }
        }
        return sum;
    }

}
